#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/8/23 15:06
# ===========================================
#       题目名称： 31. 下一个排列
#       题目地址： https://leetcode.cn/problems/next-permutation/description/
#       题目描述： https://note.youdao.com/s/RRXNSXjR
# ===========================================
import copy
import itertools as it


class Solution:
    """
        实现思路：
            1,2,3,4
            1,2,4,3
            1,3,2,4,
            1,3,4,2,

    """

    def nextPermutation(self, nums):
        """
        Do not return anything, modify nums in-place instead.
        """
        # 1. 判断是否是最大的数
        max_nums = list(nums)
        max_nums.sort(reverse=True)
        if nums == max_nums:
            # 默认从小到大排序
            nums.sort()
        else:
            cur_len = 2  # 当前定义的长度
            is_find = False  # 是否找到
            while cur_len <= len(nums) and not is_find:
                cur_nums = tuple(copy.deepcopy(nums[len(nums) - cur_len:]))

                # 序列中取2个元素进行排列 找出比当前这几个大的 进行替换
                small_dict = {}
                for tmp_tup in it.permutations(nums[len(nums) - cur_len:], cur_len):
                    tmp_nums = copy.deepcopy(tmp_tup)
                    # 比较 cur_nums 和 tmp_nums
                    if cur_nums < tmp_nums:
                        small_dict[tmp_nums] = tmp_tup
                if small_dict:
                    is_find = True
                    tmp_list = list(small_dict[sorted(small_dict.keys())[0]])
                    for index in range(len(nums) - cur_len, len(nums)):
                        nums[index] = tmp_list[0]
                        tmp_list.pop(0)
                cur_len += 1
        print(nums)


if __name__ == '__main__':
    s = Solution()
    # [1,3,2]
    s.nextPermutation(nums=[1, 2, 3])
    # [1,2,3]
    s.nextPermutation(nums=[3, 2, 1])
    # [1,5,1]
    s.nextPermutation(nums=[1, 1, 5])
